package java学习.算法.二叉树;

import java.util.ArrayList;
import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/7 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 二叉树的下一个结点 {

     class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode target = pNode;
         if (target==null){
             return null;
         }
        TreeLinkNode root = getroot(target);

        Stack<TreeLinkNode> s = new Stack<>();
        ArrayList<TreeLinkNode> list = new ArrayList<>(); // 把遍历的结果存储下来。
        s.push(root);

        while (!s.isEmpty()){
            while (root!=null){
                s.push(root.left);
            }
            TreeLinkNode node = s.pop();
             list.add(node);
             node = node.right;
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).val == target.val){
                return  list.get(i+1);
            }
        }
       return null;
    }
     public TreeLinkNode getroot(TreeLinkNode pNode){
         TreeLinkNode left = getroot(pNode.left);
         TreeLinkNode right = getroot(pNode.right);
         TreeLinkNode next = getroot(pNode.next);
         if (left==null&&right==null&&next==null){
             return null;
         }
         if (next!=null){
             while (next!=null){
                 pNode = pNode.next;
             }
         }
         return pNode;
     }
}

